package newcoder.JZ51;

//在数组中的两个数字，如果前面一个数字大于后面的数字，
//则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
//题目保证输入的数组中没有的相同的数字

//数据范围：  对于 50\%50% 的数据, size\leq 10^4size≤10
//        4
//
//        对于 100\%100% 的数据, size\leq 10^5size≤10
//        5
//
//        数组中所有数字的值满足 0 \le val \le 10000000≤val≤1000000
//输入： [4,2,8,9,5,5,6,7,0]
//返回 7
public class Solution {
    public static int InversePairs(int[] array) {
        int min = array[0];
        int max = array[0];
        long p = 0;
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                p = p + i;
                min = array[i];
            } else if (array[i] > max) {
                max = array[i];
            } else {
                for (int j = 0; j < i; j++) {
                    if (array[j] > array[i]) {
                        p++;
                    }
                }
            }

        }
        System.out.println(p);
        return (int) (p % 1000000007);
    }

    public static int mergeSort(int[] array) {
        return 0;
    }

    public void sort(int[] array, int left, int right) {
        System.out.println(left+","+right);
        if (left >= right) {
            return;
        }
        if (left == right - 1) {
            if (array[left] > array[right]) {
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
            }
            return;
        }
        int middle = (left+right) / 2;
        sort(array, left, middle);
        sort(array, middle + 1, right);
        merge(array, middle,left,right);
    }

    public void merge(int[] array, int middle,int left,int right) {
            int[] temp = new int[right-left+1];
            int pl =left,pr = middle+1;
        for (int i = 0; i < temp.length; i++) {
            if (pl<=middle && pr <=right){
                if (array[pl]>array[pr]){
                    temp[i] = array[pr];
                    pr++;
                }
                else{
                    temp[i] = array[pl];
                    pl++;
                }
            }
            else if(pl<=middle){
                temp[i] = array[pl];
                pl++;
            }
            else{
                temp[i] = array[pr];
                pr++;
            }
        }
        for (int i = 0; i < temp.length; i++) {
            array[left+i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] a = {3,2,1,7,3,5,1,8,4};
//        sort(a,0,a.length-1);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
//        System.out.println(InversePairs(a));
//        System.out.println(-13% 5);
    }
}
